package leetcode_day._2022._202204;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/2 0:17
 * 二倍数对数组
 * 算法：堆
 * 如果数组的数都大于 0，那么直接排序即可，但是数组中有小于 0 的数
 * 根据与 0 的距离来将数据放入堆中
 * 如果 x 没有被预定过，那么 x 必然是较小值，此时给 x 预定一个 2 * x，即对 2 * x 的预定次数 +1
 * 如果 x 被预定过，对 x 的预定次数 -1
 */
public class _01_954 {
    public static void main(String[] args) {
        System.out.println(new _01_954().canReorderDoubled(new int[]{2, 4, 0, 0, 8, 1}));
    }

    static int N = 100010, M = 2 * N;
    static int[] CNT = new int[2 * M];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(CNT, 0);
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(Math::abs));
        for (int num : arr) queue.add(num);
        while (!queue.isEmpty()) {
            int poll = queue.poll(), t = 2 * poll;
            if (CNT[poll + M] != 0 && --CNT[poll + M] >= 0) continue;
            ++CNT[t + M];
        }
        for (int i = 0; i < 2 * M; i++) if (CNT[i] != 0) return false;
        return true;
    }

}
